package cn.leetcode;

import java.util.Stack;

public class Code206 {
    public static ListNode reverseList(ListNode head) {
        if(head != null){
            if(head.next != null){
                ListNode listNode = reverseList(head.next);
                head.next.next = head.next;
                head.next = null;
                return listNode;
            }else{
                return head;
            }
        }
        return null;
    }


     public static ListNode reverseList2(ListNode head) {
         ListNode listNode;
         if(head==null || head.next==null){
             return head;
         }else {
             listNode = reverseList2(head.next);
             head.next.next = head;
         }
         return listNode;
     }

    public static ListNode reverseList3(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode pop = stack.pop();
        ListNode result = pop;
        while (stack.size() != 0){
            ListNode flag = pop;
            pop = stack.pop();
            flag.next = pop;
            pop.next = null;
        }
        return result;
    }
}


